package leetcode.p752;

import javafx.util.Pair;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * @author: trtan
 * @date: 2021-06-25 06:53
 **/
public class OpenTheLock {
    public static void main(String[] args) {
        System.out.println(new OpenTheLock().openLock(new String[]{"8888"}, "0009"));
    }
    /**
     * 直接bfs依次枚举就行
     * @param deadends
     * @param target
     * @return int
     * @author trtan
     * @date 2021/6/25 7:21
     */
    public int openLock(String[] deadends, String target) {
        Queue<int[]> que = new LinkedList<>();
        Map<String, Boolean> vis = new HashMap<>();
        for (int i = 0; i < deadends.length; i++) {
            vis.put(deadends[i], true);
        }
        if (vis.get("0000") == null) {
            que.offer(new int[]{0, 0, 0, 0, 0});
            vis.put("0000", true);
        }
        while (!que.isEmpty()) {
            int[] top = que.poll();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 4; i++) {
                sb.append(top[i]);
            }
            System.out.println(sb.toString() + ", " + top[4]);
            if (target.equals(sb.toString())) {
                return top[4];
            }
            for (int i = -1; i <= 1; i += 2) {
                for (int j = 0; j < 4; j++) {
                    int p = top[j] + i;
                    if (p == -1) {
                        p = 9;
                    }
                    if (p == 10) {
                        p = 0;
                    }
                    StringBuilder s = new StringBuilder();
                    for (int k = 0; k < 4; k++) {
                        if (k == j) {
                            s.append(p);
                        } else {
                            s.append(top[k]);
                        }
                    }
                    if (vis.get(s.toString()) == null) {
                        int[] t = new int[5];
                        for (int k = 0; k < 4; k++) {
                            if (k == j) {
                                t[k] = p;
                            } else {
                                t[k] = top[k];
                            }
                        }
                        t[4] = top[4] + 1;
                        System.out.println("=======>" + s + ", " + t[4]);
                        que.offer(t);
                        vis.put(s.toString(), true);
                    }
                }
            }
        }
        return -1;
    }
}

